home *** CD-ROM | disk | FTP | other *** search
/ Linux Cubed Series 3: Developer Tools / Linux Cubed Series 3 - Developer Tools.iso / devel / lang / c / c-bat-0.1n / c-bat-0 / c-bat-0.1 / src / hash.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-06-16  |  7.2 KB  |  386 lines
  1. /* hash.c */
  2.  
  3. #include <stdio.h>
  4. #include <stdlib.h>
  5. #include <string.h>
  6. #include <math.h>
  7. #include <malloc.h>
  8.  
  9. #include "hash.h"
  10.  
  11.  
  12.  
  13. static long HashSize; 
  14. t_hash_table HashTable;        /* static schlecht fuer MSC */ 
  15.  
  16.  
  17. static char *HashFileName = "symbols";
  18. static long MaxSearch;        /* Suche nach freiem Platz in HashTable */
  19.  
  20.  
  21.  
  22.  
  23.  
  24. /******************************************************************/
  25. /* Verwaltung Hashtabelle: INIT, SAVE, LOAD                       */
  26. /******************************************************************/
  27.  
  28. void init_hashtable (void)
  29. {
  30.     long i;
  31.  
  32.     /* HashSize berechnen: Primzahl < SZE_HASH_TABLE */
  33.  
  34.     HashSize = SZE_HASH_TABLE;
  35.  
  36.     /* Tabelle loeschen: */
  37.  
  38.     for (i=0; i<HashSize; i++) 
  39.     {
  40.         HashTable[i].ident = NULL;    /* Token frei */
  41.         HashTable[i].type  = 0;
  42.         HashTable[i].flags = 0;
  43.         HashTable[i].data  = NULL;
  44.     }
  45.  
  46.     MaxSearch = 0;
  47. }
  48.  
  49. long save_hashtable (void)
  50. {
  51.     long i, cnt = 0;
  52.     FILE *fp;
  53.  
  54.     fp = fopen (HashFileName, "w");
  55.     if (!fp) 
  56.     {
  57.         fprintf( stderr, "error opening symbol file ");
  58.         fprintf( stderr, "%s\n", HashFileName);
  59.     }
  60.  
  61.     for (i=0; i<HashSize; i++)
  62.     {
  63.             if (HashTable[i].ident)
  64.         {
  65.             fprintf (fp, "%ld %ld %hd %s\n",
  66.                 i,
  67.                 HashTable[i].type,
  68.                 HashTable[i].flags,
  69.                 HashTable[i].ident );
  70.             cnt++;
  71.         }
  72.     }
  73.  
  74.     fclose (fp);
  75.  
  76.     return (cnt);
  77. }
  78.  
  79. long load_hashtable (void)
  80. {
  81.     long i, dummy, cnt = 0;
  82.     FILE *fp;
  83.     char buf[200], str[5][100], *status;
  84.  
  85.     fp = fopen (HashFileName, "r");
  86.     if (!fp) 
  87.     {
  88.         fprintf( stderr, "error opening symbol file %s \n",
  89.                          HashFileName);
  90.     }
  91.  
  92.     while (1)
  93.     {
  94.         status = fgets (buf, 199, fp);
  95.         if (status == NULL) break;
  96.  
  97.         sscanf (buf, "%ld", &i);
  98.  
  99.         sscanf (buf, "%s%s%s%s%s", str[0], str[1], str[2],
  100.                 str[3], str[4] );
  101.  
  102.         HashTable[i].type = atoi (str[1]);
  103.         HashTable[i].flags = (short) atoi (str[2]);
  104.  
  105.         HashTable[i].ident = malloc (strlen (str[4]) + 1);    /* null char ! */
  106.         if (HashTable[i].ident == NULL)
  107.             fprintf(stderr, "error load_hashtable\n");
  108.         strcpy (HashTable[i].ident, str[4]);
  109.  
  110.         cnt++;
  111.     }
  112.  
  113.     fclose (fp);
  114.  
  115.     return (cnt);
  116. }
  117.  
  118. long hash_search_steps (void)
  119. {
  120.     return (MaxSearch);
  121. }
  122.  
  123.  
  124. /******************************************************************/
  125. /* Hash-Algorithmus (nicht optimiert):                            */
  126. /******************************************************************/
  127.  
  128. static long hash (char *ident)
  129. {
  130.     long i, s = 0;
  131.     
  132. /*    printf ("hash call '%s'\n", ident);
  133. */
  134.     for (i=0; i<strlen(ident); i++)
  135.         s += (unsigned char)ident[i];
  136.     s *= 3;
  137.  
  138.     i = s % HashSize;
  139.  
  140.     if (i > HashSize) fprintf( stderr, "hash error\n");
  141.  
  142. /*    printf ("hash result: %ld\n", i);
  143. */
  144.     return (i);
  145. }
  146.  
  147.  
  148. /******************************************************************/
  149. /* Zugriffe auf Hashtabelle: SEARCH, INSERT, UPDATE, GET, CLEAR   */
  150. /******************************************************************/
  151.  
  152. long search_token (char *ident, t_hash_data *data)
  153. {
  154.     long index, index_old;
  155.     short found = FALSE;
  156.  
  157.     if (!ident[0]) 
  158.     {
  159.         return (TOKEN_NOT_FOUND);
  160.     }
  161.  
  162.     if (strlen (ident) >= SZE_HASH_IDENT)
  163.     {
  164.         fprintf(stderr, "hash warning: ident size overflow\n");
  165.         ident [SZE_HASH_IDENT - 1] = 0;
  166.     }
  167.  
  168.     index = hash (ident);
  169.     index_old = index;
  170.  
  171.     if (!HashTable[index].ident)
  172.     {
  173.         return (TOKEN_NOT_FOUND);
  174.     }
  175.  
  176.     /* Eintrag suchen: */
  177.  
  178.     found = FALSE;
  179.     
  180.     while (!found)
  181.     {
  182.         if (!HashTable[index].ident) break;
  183.         else
  184.         {
  185.             if (strcmp (ident, HashTable[index].ident) == 0)
  186.             {
  187.                 found = TRUE;
  188.                 break;
  189.             }
  190.             else
  191.             {
  192.                 index++;
  193.                 if (index >= HashSize) index = 0;
  194.                 if (index == index_old) break;
  195.             }
  196.         }
  197.     }
  198.  
  199. /*    printf (">%s<  >%s<  %ld  %d\n", ident, HashTable[index].ident, index, found);
  200. */
  201.  
  202. /*    if (found)
  203.         printf ("hash: data '%s' found (index = %d)\n", ident, index);
  204.     else
  205.         printf ("hash: data '%s' not found (index = %d)\n", ident, index);
  206. */
  207.  
  208.  
  209.     if (found)
  210.     {
  211.         /* Hashtabelle lesen: */
  212.  
  213.         if( data )
  214.                   { strcpy (data->ident, HashTable[index].ident);
  215.             data->type = HashTable[index].type;
  216.             data->flags = HashTable[index].flags;
  217.             data->data  = HashTable[index].data;
  218.                    }
  219.  
  220.         return (index);
  221.     }
  222.     else
  223.         return (TOKEN_NOT_FOUND);
  224. }
  225.  
  226. long insert_token (t_hash_data *data)
  227. {
  228.     long index, index_old, i = 0;
  229.  
  230.  
  231.     if (strlen (data->ident) >= SZE_HASH_IDENT)
  232.     {
  233.         fprintf( stderr, "hash warning: ident size overflow\n");
  234.         data->ident [SZE_HASH_IDENT - 1] = 0;
  235.     }
  236.  
  237.     index = hash (data->ident);
  238.     index_old = index;
  239.  
  240.     /* freien Platz suchen: */
  241.  
  242.     while (HashTable[index].ident)
  243.     {
  244.         index++;
  245.         i++;
  246.         if (index >= HashSize) index = 0;
  247.         if (index == index_old)
  248.         {
  249.             fprintf( stderr, "hash error: hashtable full ! \n");
  250.             exit (0);
  251.         }
  252.     }
  253.  
  254.     /* Anzahl der Suchschritte merken: */
  255.  
  256.     if (i > MaxSearch) MaxSearch = i;
  257.  
  258.         
  259. /*    printf ("hash: token '%s' inserted (index = %d)\n", data->ident, index);
  260. */
  261.     /* Eintrag in Hashtabelle: */
  262.  
  263.     HashTable[index].ident = malloc (sizeof(data->ident));
  264.     strcpy (HashTable[index].ident, data->ident);
  265.     HashTable[index].type  = data->type;
  266.     HashTable[index].flags = data->flags;
  267.     HashTable[index].data  = data->data;
  268.  
  269.     return (index);
  270. }    
  271.  
  272. void update_token (t_hash_data *data, long index)
  273. {
  274.     if (index >= HashSize)
  275.     {
  276.         fprintf( stderr, "\nerror update_token: index overflow\n");
  277.         exit (0);
  278.     }
  279.  
  280.     /* Eintrag in Hashtabelle: */
  281.  
  282.     free (HashTable[index].ident);
  283.     HashTable[index].ident = malloc (sizeof(data->ident));
  284.     strcpy (HashTable[index].ident, data->ident);
  285.     HashTable[index].type = data->type;
  286.     HashTable[index].flags = data->flags;
  287.     HashTable[index].data  = data->data;
  288. }    
  289.  
  290. void get_token (t_hash_data *data, long index)
  291. {
  292.     if (index >= HashSize)
  293.     {
  294.         fprintf( stderr, "\nerror get_token: index overflow\n");
  295.         exit (0);
  296.     }
  297.  
  298.     /* Hashtabelle lesen: */
  299.  
  300.     strcpy (data->ident, HashTable[index].ident);
  301.     data->type = HashTable[index].type;
  302.     data->flags = HashTable[index].flags;
  303.     data->data  = HashTable[index].data;
  304. }
  305.  
  306. void clear_token (long index)
  307. {
  308.     if (index >= HashSize)
  309.     {
  310.         fprintf( stderr, "\nerror clear_token: index overflow\n");
  311.         exit (0);
  312.     }
  313.  
  314.     free (HashTable[index].ident);
  315.     HashTable[index].ident = malloc (8);
  316.     strcpy (HashTable[index].ident, "!remvd!");
  317.  
  318.     /* es muss ein Eintrag stehen bleiben, sonst ist der schnelle
  319.        Search-Algorithmus nicht mehr moeglich (Annahme lueckenloser
  320.        Belegung der Tabelle ab hash(ident) !!) */
  321.  
  322.     HashTable[index].type = 0;
  323.     HashTable[index].flags = 0;
  324.     HashTable[index].data  = NULL;
  325. }
  326.  
  327. long create_token_id (void)
  328. {
  329.     long i;
  330.  
  331.     /* Vergabe einer virtuellen Token-ID: */
  332.  
  333.     for (i=0; i<HashSize; i++)
  334.     {
  335.         if (HashTable[i].ident) continue;
  336.  
  337.         HashTable[i].ident = malloc (8);
  338.         strcpy (HashTable[i].ident, "virtual");
  339.  
  340.         return (i);
  341.     }
  342.  
  343.     fprintf( stderr, "hash error: hashtable full ! \n");
  344.     exit (0);
  345. }
  346.  
  347.  
  348. /******************************************************************/
  349. /* Zugriffe auf Token-Flags:                                  */
  350. /******************************************************************/
  351.  
  352. void set_token_flag (long index, short flag)
  353. {
  354.     if (index >= HashSize)
  355.     {
  356.         fprintf( stderr, "\nhash error: index overflow\n");
  357.         exit (0);
  358.     }
  359.  
  360.     HashTable[index].flags = flag;
  361. }
  362.  
  363. short get_token_flag (long index)
  364. {
  365.     return ((short) HashTable[index].flags);
  366. }
  367.  
  368.  
  369. char *get_symbol (long index)
  370. {
  371.     static char str[20];
  372.  
  373.     /* Hashtabelle lesen: */
  374.         if( index == TOKEN_NOT_FOUND )
  375.     {
  376.         sprintf (str, "<--??-->");
  377.         return (str);
  378.     }
  379.     else if (!HashTable[index].ident)
  380.     {
  381.         sprintf (str, "#%ld", index);
  382.         return (str);
  383.     }
  384.     else return (HashTable[index].ident);
  385. }
  386.